#include <iostream>
template<typename T>

// 当数组近乎有序时,插入排序非常快
void insertionSort2(T arr[], int n){
	for(int i = 1; i < n; ++i){
		/**
		 * 将交换操作变成 比较后赋值
		 * 寻找arr[i] 合适的插入位置
		 */
		T e = arr[i];
		int j;			// j 保存的元素e应该插入的位置
		for(j = i; j > 0 && arr[j - 1] > e; --j){	// 前面元素比e大，循环继续
			// e 保存当前i值，如果比之前值小，则进行交换
			arr[j] = arr[j - 1];  
		}
		arr[j] = e;		// --j,此时将较小的e 向前移动
	}
}

// 对arr[l...r]范围的数组进行插入排序
template<typename T>
void insertionSort2(T arr[], int l, int r){
	for(int i = l + 1;i <= r; ++i){
		T e = arr[i];
		int j;
		for(j = i; j > l && arr[j - 1] > e; --j){
			arr[j] = arr[j - 1];
		}
		arr[j] = e;
	}
}
